package Sort;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author Liangyaoyun
 */
public class MergeSort {
    //归并排序
    public void mergeSort(int[] nums){
        if (nums.length<=1){
            return;
        }
        //减一是因为middle代表的是下标
        int middle= (nums.length-1)/2;
        //加一是因为left代表的是下标，而数组长度从1算起
        int[] left=new int[middle+1];

        for (int i = 0; i < left.length; i++) {
            left[i]=nums[i];
        }
        //middle+1代表的是左半部分数组的长度
        //显而易见，右半数组的长度自然就为数组全长减去左半部分
        int[] right=new int[nums.length-(middle+1)];

        //因为在右半部分的数组是从原数组中间开始的，所以j需要等于右半数组的下标
        //注意！j是小于总数组长度的
        for (int j = middle+1; j < nums.length; j++) {
            right[j-(middle+1)]=nums[j];
        }
        mergeSort(left);
        mergeSort(right);
        //左半数组的起始位置
        int i=0;
        //右半数组的起始位置
        int j=0;
        //原数组的下标
        int k=0;
        while (i<left.length&&j< right.length){
            if (left[i]<=right[j]){
                nums[k]=left[i];
                i++;
            }else {
                nums[k]=right[j];
                j++;
            }
            k++;
        }
        while (i<left.length){
            nums[k++]=left[i++];
        }
        while (j<right.length){
            nums[k++]=right[j++];
        }
        for (int l = 0; l < nums.length; l++) {
            if (nums[l]== nums.length-1){
                System.out.println(nums[l]);
            }else {
                System.out.print(nums[l]+" ");
            }
        }
    }

}
